import tool.*;
import tool.TreeNode;

import java.lang.annotation.Target;
import java.util.*;

/**
 * @Description: 找树左下角的值
 * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * 假设二叉树中至少有一个节点。
 * @Date:Create in 16:12  2022/6/22
 */
public class findBottomLeftValue0513 {
    public static void main(String[] args) {
        String s = "[1,2,3,4,null,5,6,null,null,null,null,7,8]";
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
//        testIf();
//        bfs(root);
//        testGetFirst();
        System.out.println(findBottomLeftValue1(root));
    }

    public static int findBottomLeftValue1(TreeNode root) {
        if(root == null){
            return -1;
        }
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();

        queue.add(root);
        //返回的是int，为什么要用treenode类型来存，如果你找到了一个可能的目标，把val存下来就行了
        TreeNode taget = new TreeNode(-1);
        int target = -1;
        while(!queue.isEmpty()){
            int size = queue.size();
            System.out.println("queue size is \t"+size);
//            对于queue来说，只要会poll和add就行了，其他的不要用，不要调用太多api
            for(int i=0;i<size;i++){

                TreeNode cur = queue.poll();
                if(i==0){
                    target = cur.val;
                }
                if(cur.left!=null){
                    queue.add(cur.left);
                }
//                巨大错误，我一个树只能有一个节点吗？？？？？？
                if(cur.right!=null) {
                    queue.add(cur.right);
                }
            }
        }
        return target;
    }

    public static void bfs(TreeNode root){
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            System.out.println(size);
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left!=null)
                    queue.add(cur.left);
                if (cur.right!=null)
                    queue.add(cur.right);
            }
        }
    }

    public static void testIf(){
        int a = 2;
        int b = 3;
        if (a == 2){
            System.out.println("a == 2");
        }
        //这里的第二个会运行吗？
        //这个的意思就是我a == 2的时候b就不能是3了，if前面的判断进去来，后面就不会再进去来
        else if (b == 3){
            System.out.println("b == 3");
        }
    }

    public static void testGetFirst(){
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer> list3 = new ArrayList<>();
        list3.add(5);
        list3.add(6);
        List<Integer> list4 = new ArrayList<>();
        list4.add(7);
        list4.add(8);
        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        lists.add(list4);
        int target = -1;
        //找到最后一层的list的第一个节点7
        for (int i = 0; i < lists.size(); i++) {
            //第一个就是get（0）
            //现在就是找到最后一层的第一个怎么找
            //如果我不知道多少层怎么办？
            int a = lists.get(i).get(0);
            //你看这样行不行
            target = a;
        }
        System.out.println(target);
        //写

    }
}
